/*
 * Copyright 2010 Christoph Widulle (christoph.widulle@googlemail.com)
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
 * License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS"
 * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 */



package com.android1.amarena2d.commons.collections;

public class FixedSizeMap<K, V> {

    private final K[] keys;
    private final V[] values;

    private int size;
    private int lastSearchIndex;

    @SuppressWarnings("unchecked")
    public FixedSizeMap(final int maxEntries) {
        keys = (K[]) new Object[maxEntries];
        values = (V[]) new Object[maxEntries];
    }

    public boolean isFull() {
        return size == keys.length;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean containsKey(final K key) {
        return findKey(0, key) != -1;
    }

    public boolean containsValue(final V value) {
        return findValue(0, value) != -1;
    }

    public V get(final K key) {
        // Search for key
        final int index = findKey(key);

        if (index != -1) {
            // Return value
            return values[index];
        }

        // Failed to find key
        return null;
    }

    public V getValue(int index) {
        return values[index];
    }

    public V put(final K key, final V value) {
        // Search for key
        final int index = findKey(key);

        if (index != -1) {
            // Replace existing value
            final V oldValue = values[index];
            values[index] = value;
            return oldValue;
        }

        // Is there room for a new entry?
        if (size < keys.length) {
            // Store at first null index and continue searching after null index
            // next time
            final int nullIndex = nextNullKey(lastSearchIndex);
            lastSearchIndex = nextIndex(nullIndex);
            keys[nullIndex] = key;
            values[nullIndex] = value;
            size++;

            return null;
        } else {
            throw new IllegalStateException("Map full");
        }
    }

    public V remove(final Object key) {
        // Search for key
        final int index = findKey(key);

        if (index != -1) {
            // Store value
            final V oldValue = values[index];

            keys[index] = null;
            values[index] = null;
            size--;

            return oldValue;
        }

        return null;
    }


    public void clear() {
        for (int i = 0; i < keys.length; i++) {
            keys[i] = null;
            values[i] = null;
        }

        size = 0;
    }


    public int getSize() {
        return size;
    }


    private int nextIndex(final int index) {
        return (index + 1) % keys.length;
    }


    private int nextKey(final int start) {
        int i = start;

        do {
            if (keys[i] != null) {
                return i;
            }

            i = nextIndex(i);
        }
        while (i != start);

        return -1;
    }


    private int nextNullKey(final int start) {
        int i = start;

        do {
            if (keys[i] == null) {
                return i;
            }

            i = nextIndex(i);
        }
        while (i != start);

        return -1;
    }


    private int findKey(final Object key) {
        if (size > 0) {
            // Find key starting at search index
            final int index = findKey(lastSearchIndex, key);

            // Found match?
            if (index != -1) {
                // Start search at the next index next time
                lastSearchIndex = nextIndex(index);

                // Return index of key
                return index;
            }
        }

        return -1;
    }


    private int findKey(final int start, final Object key) {
        int i = start;

        do {
            if (key.equals(keys[i])) {
                return i;
            }

            i = nextIndex(i);
        }
        while (i != start);

        return -1;
    }

 
    private int findValue(final int start, final Object value) {
        int i = start;

        do {
            if (value.equals(values[i])) {
                return i;
            }

            i = nextIndex(i);
        }
        while (i != start);

        return -1;
    }
}
